"""
5.最长回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring

给你一个字符串 s，找到 s 中最长的回文子串。

示例:
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
"""
class Solution:
  """
  设:
    函数 f(n) 返回一个升序排列的包含所有结果的 int[]，其任意元素 i, 都使得 s[i:n+1] 为回文字符串
  则:
    longestPalindrome(s) == maxByLen(s[f(0)[0], 1]...s[f(n)[0], n+1])

    f(n) = {
      [0]  #(当 n = 0 时),
      [i-1 for i in f(n-1) if s[i-1] == s[n]] + [n-1 if s[n-1] == s[n]] + [n]
    }
  """
  def longestPalindrome(self, s: str) -> str:
    # 创建dp表，使得 dp[n] 中的任一元素 i 都满足 s[i:n+1] 为回文字符串
    dp = [[0]] # 满足 s[i:1] 为回文字符串的 i 有且仅有一个值: 0
    si = 0 # 起始索引
    ei = 0 # 结束索引
    l = 0 # 长度
    # 动态规划
    for n in range(1, len(s)):
      v = [i-1 for i in dp[n-1] if i > 0 and s[i-1] == s[n]]
      if s[n-1] == s[n]:
        v.append(n-1)
      v.append(n)
      dp.append(v)
      x = v[0]
      y = n - x
      # 获取最大长度时的起始索引与结束索引
      if y > l:
        si = x
        ei = n
        l = y
    return s[si:ei+1]
